home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c / pro12 / isort.c < prev    next >
C/C++ Source or Header  |  1990-12-26  |  2KB  |  70 lines
  1. /***********************************************************************/
  2. /*  isort(): Non-Recursive Insertion Sort function.                    */
  3. /*  See the function declaration for calling information.              */
  4. /* Function is by Bruce Feist; please contact me on CompuServe with    */
  5. /*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
  6. /*    questions or problems.                                           */
  7. /* You can also reach me at the Enlightened Board, at (703) 370-9528,  */
  8. /*   N/8/1                                                             */
  9. /* Feel free to make use of this code in your own programs.            */
  10. /***********************************************************************/
  11.  
  12. /* Insertion sort.  Boring, but effective on small arrays. */
  13. /* Do NOT use this on a randomly-ordered, large array.     */
  14.  
  15. #include <alloc.h>
  16. #include <mem.h>
  17. #include <stddef.h>
  18. #include <stdio.h>
  19.  
  20. #include "sort.h"
  21.  
  22. static char *base;
  23. static int nelem, width;
  24. static int (*compare) (void *, void *);
  25.  
  26. int
  27. isort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
  28. {
  29.   char *temp_record, *left_ptr, *right_ptr, *last_ptr;
  30.  
  31.   base = pbase;
  32.   nelem = pnelem;
  33.   width = pwidth;
  34.   compare = pcompare;
  35.  
  36.   temp_record = malloc (width);
  37.   if (temp_record == NULL)
  38.     return S_NOMEM;
  39.  
  40.   last_ptr = base + (nelem - 1) * width;
  41.  
  42.   /* This loop assumes that the first i-1 entries are in order. */
  43.   /* It then positions the ith entry in their midst, so that the */
  44.   /* first i entries are in order. */
  45.  
  46.   for (right_ptr = base + width;
  47.        right_ptr <= last_ptr;
  48.        right_ptr += width)
  49.   {
  50. #if VERBOSE
  51.     printf ("Pass # %d\n", (right_ptr - base) / width);
  52. #endif
  53.     memcpy (temp_record, right_ptr, width);
  54.  
  55.     /* This loop finds out where the new entry we're trying */
  56.     /* to position belongs.                                 */
  57.  
  58.     for (left_ptr = right_ptr - width;
  59.          left_ptr >= base && compare (left_ptr, right_ptr) > 0;
  60.          left_ptr -= width)
  61.       ;
  62.  
  63.     left_ptr += width;
  64.     memmove (left_ptr + width, left_ptr,    (size_t) (right_ptr - left_ptr));
  65.     memcpy (left_ptr,         temp_record, width);
  66.     } /* end for right_ptr */
  67.  
  68.   free (temp_record);
  69.   return S_OK;
  70.   }  /* end isort */